package listbyorder.access101_200.test133;

import java.util.ArrayList;
import java.util.HashMap;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/11 10:09
 */
public class Solution3 {

    // 方法三： DFS求解
    public Node cloneGraph(Node node) {
        if (node == null) return node;
        HashMap<Integer, Node> map = new HashMap<>();
        return dfs(node, map);
    }

    private Node dfs(Node node, HashMap<Integer, Node> map) {
        if (map.containsKey(node.val)) {
            return map.get(node.val);
        }

        Node n = new Node();
        n.val = node.val;
        n.neighbors = new ArrayList<>();
        map.put(node.val, n);
        for (Node neighbor : node.neighbors) {
            n.neighbors.add(dfs(neighbor, map));
        }
        return n;
    }
}
